package swardToOffer.struct_4_tree;

/**
 * @Author ChanZany
 * @Date 2021/5/19 20:15
 * @Version 1.0
 * <p>
 * 面试题8：二叉树的下一个结点
 * 题目：给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？
 * 树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。
 * 思路：
 * 1. 当当前节点存在右子树的时候，中序遍历的下一个结点为右子树的最左节点。
 * 2. 当节点不存在右子树的时候，中序遍历的下一个结点必定为该节点的父辈节点。但是究竟是哪一辈呢？
 * 根据中序遍历特性，如果当前节点是父的左子节点，则下一个节点一定是父节点，
 * 左父结点一定已经被中序遍历访问过，所以下一个结点一定是在父节点路径上的第一个右父节点。
 */
public class FindNextNode {
    public TreeLinkNode getNext(TreeLinkNode node) {
        if (node == null) return null;
        if (node.right != null) {
            node = node.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        } else {
            while (node.parent != null) {
                if (node.parent.left == node) { //当前节点为左子节点时，下一个节点为父节点
                    return node.parent;
                }
                node = node.parent; //核心代码
            }
        }
        return null;
    }

    public static void main(String[] args) {
        FindNextNode Main = new FindNextNode();
        TreeLinkNode node1 = new TreeLinkNode(1);
        TreeLinkNode node2 = new TreeLinkNode(2);
        TreeLinkNode node3 = new TreeLinkNode(3);
        TreeLinkNode node4 = new TreeLinkNode(4);
        TreeLinkNode node5 = new TreeLinkNode(5);
        TreeLinkNode node6 = new TreeLinkNode(6);
        TreeLinkNode node7 = new TreeLinkNode(7);
        TreeUtil.connectLinkedTree(node1,node2,node3);
        TreeUtil.connectLinkedTree(node2,node4,node5);
        TreeUtil.connectLinkedTree(node3,node6,node7);
//        TreeUtil.LevelTraversal2(node1);
        System.out.println(Main.getNext(node5).val);
    }
}
